﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Aggregation_Clustering
{
    class ClusterList
    {
        public ClusterList()
        {
            clusterList = new ArrayList();
            elementList = new ArrayList();
            //set the dummyCluster
            clusterList.Add(new Cluster());
        }
        //初始化所有S个Cluster以及初始值
        public void InitClusters(int s,int ubound=10,int lbound=2)
        {
            numS = s;
            
            UBound = ubound;
            LBound = lbound;
            Cluster DCluster = (Cluster)clusterList[0];
            numT = DCluster.num;//number of the elements in dummyCluster

            MoveVal = new double[numT + 1, numS + 1];//注意其实有s个cluster' 和1个Dcluster
            AddVal = new double[numT + 1, numS + 1];//注意其实有s个cluster' 和1个Dcluster
            Value = new double[numS + 1];

            for (int i = 0; i < numS; i++)
            {
                clusterList.Add(new Cluster());
            }
            ObjVal = 0;//将最初的cluster价值设为0
            StartWeight = 0.7;//初始权重(为凸显某个因素的权)设为0.7
            Weight = StartWeight;//weight不用求
            //printf “Initial Threshold Test Weight = ” StartWeight // Foregoing print is to report the initial value of Weight used in the Threshold Test 
            large = double.MaxValue;

            //set elements' ID in initialization


        }

        //4.3 First create 2-element clusters.
        public void Create2EleClusters() { 
            //calculate the CheckBound
            Cluster DCluster = (Cluster)clusterList[0];
            numT = DCluster.num;//number of the elements in dummyCluster
            int CheckBound = numT / numS;
            if (CheckBound >= 7)
                CheckBound = CheckBound - 2;
            CheckBound = Min(CheckBound, 10);//每个cluster中最多有10个元素
            ///////////////////////////////////////////////////////////////////
            ////////////////////////////////////////////////////////////////////////////////

            Element elementT0Best=null,elementT1Best=null,elementT2Best=null,elementT3Best=null;
            Element elementT0 = null, elementT1 = null, elementT2 = null, elementT3 = null;
            int TLeft;

            #region 填装所有CLuster
            for (int s = 1; s <= numS; s++)
            {
                double BestSumScore = double.MaxValue;

                elementT0 = DCluster.First;
                #region//Endwhile (t0 > 0)//当此次循环结束时当前Cluster（s）所有点的最优组合（t1,t2,t3,t0）就已找到。
                while (elementT0 != null)
                {
                    double Best1 = double.MaxValue;
                    double Best2 = double.MaxValue;
                    double Best3 = double.MaxValue;
                    elementT1 = null;
                    elementT2 = null;
                    elementT3 = null;
                    // for each t0, find the three best scores Score(t0,t1), Score(t0,t2) and Score(t0,t3). 

                    Element elementTCheck = DCluster.First;


                    #region//当这个while循环结束后对于固定t0已经找到了最小的
                    while (elementTCheck != null)
                    {
                        if (elementTCheck != elementT0)
                        {
                            double TrialVal = CalculateScore(elementT0, elementTCheck);
                            if (TrialVal < Best3)
                            {
                                if (TrialVal < Best2)
                                {
                                    Best3 = Best2;
                                    elementT3 = elementT2;
                                    if (TrialVal < Best1)
                                    {
                                        Best2 = Best1;
                                        elementT2 = elementT1;
                                        Best1 = TrialVal;
                                        elementT1 = elementTCheck;
                                    }
                                    else
                                    {
                                        Best2 = TrialVal;
                                        elementT2 = elementTCheck;
                                    }
                                }
                                else {
                                    Best3 = TrialVal;
                                    elementT3 = elementTCheck;
                                }
                            }
                        }
                        elementTCheck = elementTCheck.After;
                    }
                    #endregion

                    if (elementT3 == null)
                    {
                        Best3 = 0;
                    }
                    if (elementT2 == null)
                    {
                        Best2 = 0;
                    }
                    if (elementT1 == null)
                    {
                        Best1 = 0;
                    }
                    
                    double SumScore = Best1 + Best2 + Best3;// Score(t0,t1), Score(t0,t2) ,Score(t0,t3)
                    if (SumScore < BestSumScore){//若此时的SumScore小于之前的最优和
                        BestSumScore = SumScore; //则用新的结果更新最优和
                        elementT0Best = elementT0;
                        elementT1Best = elementT1;
                        elementT2Best = elementT2;
                        elementT3Best = elementT3;//记录t0的最优组合
                    }

                    elementT0 = elementT0.After;
                }
                #endregion
                double Try1 = double.MaxValue;
                double Try2 = double.MaxValue;
                double Try3 = double.MaxValue;
                //only has t0 left
                if (elementT1Best != null&&elementT2Best != null)
                {
                    Try1 = CalculateScore(elementT0Best, elementT1Best) + CalculateScore(elementT0Best, elementT2Best) + CalculateScore(elementT1Best, elementT2Best);
                }
                if (elementT1Best != null && elementT3Best != null)
                {
                    Try2 = CalculateScore(elementT0Best, elementT1Best) + CalculateScore(elementT0Best, elementT3Best) + CalculateScore(elementT1Best, elementT3Best);
                }
                if (elementT2Best != null && elementT3Best != null)
                {
                    Try3 = CalculateScore(elementT0Best, elementT2Best) + CalculateScore(elementT0Best, elementT3Best) + CalculateScore(elementT2Best, elementT3Best);
                }
                #region 找出当前t0下最优的t1和t2
                elementT0 = elementT0Best;
                if (Try1 <= Try2 && Try1 <= Try3)//try1 is the best
                {
                    elementT1 = elementT1Best;
                    elementT2 = elementT2Best;
                }
                else {
                    if (Try2 <= Try1 && Try2 <= Try3)//try2 is the best
                    {
                        elementT1 = elementT1Best;
                        elementT2 = elementT3Best;
                    }
                    else
                    {
                        if (Try3 <= Try1 && Try3 <= Try2)//try3 is the best
                        {
                            elementT1 = elementT2Best;
                            elementT2 = elementT3Best;
                        }
                    }
                }
                // Now the pair t0,t1 creates the next 2-element Cluster(s)
                // Remove t0 and t1 from the dummy Cluster(0)
                #endregion

                #region 找出T1、T2中相对更优的T1
                if (CalculateScore(elementT0, elementT1) > CalculateScore(elementT0, elementT2))
                {
                    elementT1 = elementT2;
                }
                #endregion

                //
                // Now the pair t0,t1 creates the next 2-element Cluster(s)
                // Remove t0 and t1 from the dummy Cluster(0)
                elementT0.MoveTo(this, s);
                elementT1.MoveTo(this, s);

                //define the 2 unused parameters 
                //double SumMoveVal = 0.0;
                //double BestMoveVal = double.MaxValue;

                Element t = DCluster.First;
                while (t != null)
                {
                    AddVal[t.ElementID,s] = CalculateScore(t, elementT0) + CalculateScore(t, elementT1);
                    t = t.After;
                }

                #region Fill rest of Cluster s up to size CheckBound
                if (s < numS)
                {
                    Cluster sCluster= getClusterbyID(s);
                    #region 该循环将当前Cluster填装至CheckBound
                    while (sCluster.num < CheckBound)
                    {
                        double BestVal = double.MaxValue;
                        Element tBest = null;
                        Element tCheck = DCluster.First;
                        double TrialVal;
                        while (tCheck != null)
                        {
                            TrialVal = AddVal[tCheck.ElementID, s];
                            if (TrialVal < BestVal)
                            {
                                BestVal = TrialVal;
                                tBest = tCheck;
                            }
                            tCheck = tCheck.After;
                        }
                        // Now add tBest to Cluster(s) by first dropping from Cluster(s0) 
                        tBest.MoveTo(this, s);

                        // Now update AddVal array.
                        t = DCluster.First;
                        while (t != null)
                        {
                            AddVal[t.ElementID, s] = AddVal[t.ElementID, s] + CalculateScore(t, tBest);
                        }
                    }
                    #endregion
                }
                #endregion
            }
            #endregion
            //所有Cluster填装完毕
            //如果CheckBound大于2 则将其他元素回归

            #region 回归大于2的元素
            if (CheckBound > 2)
            {
                Element t0First, tsFirst, t0Last;//这些值在算法中用于整段的移动Element链到DCluster中
                //程序中用不到
                for (int s = 1; s < numS; s++)
                {
                    Cluster sCluster = getClusterbyID(s);
                    t0First = sCluster.First;
                    for (int CheckSet = 0; CheckSet < CheckBound - 2; CheckSet++)
                    {
                        Element t = sCluster.First;
                        t.MoveTo(this, 0);
                    }
                    tsFirst = sCluster.First;
                    t0Last = tsFirst.Before;

                }
            }
            #endregion

            //     ObjVal = 0.0 from Initialization
            // 	Create arrays for each 2-element Cluster s
            for (int s = 1; s <= numS; s++)
            {
                Cluster sCluster = getClusterbyID(s);
                Element t0 = sCluster.First;
                Element t1 = t0.After;
                double sValue = CalculateScore(t0, t1);
                Value[s] = sValue;
                //无意义的操作= =

                ObjVal += sValue;////////////ObjVal is defined in Chapter2   
                ///////////////////////////////////////////////////////////ObjVal = ∑ (FullValue(s): s = 1 to NumS)

                sCluster.num = 2;
                sCluster.NumberLinks = 1;

                //遍历求得两个矩阵值
                for (int i = 0; i <= numS; i++)
                {
                    Cluster tempCluster = getClusterbyID(i);
                    Element tempElement = tempCluster.First;
                    while (tempElement != null)
                    {
                        AddVal[tempElement.ElementID, s] = CalculateScore(tempElement, t0) + CalculateScore(tempElement, t1);
                        MoveVal[tempElement.ElementID, s]=(sValue + AddVal[tempElement.ElementID, s])/3.0 - sValue;//在下面会用到
                        tempElement = tempElement.After;
                    }

                }
            }
            TLeft = numT - 2 * numS;
            try
            {
                CompleteTheInit(TLeft);
            }
            catch (Exception e)
            {
                throw e;
            }
        }

        public void CompleteTheInit(int tleft)
        {
            int CheckBound;
            if(tleft!=numT-2*numS){
                throw new Exception("ERROR: TLEFT is wrong."+
                    " TLEFT ="+tleft.ToString()+
                    " numT ="+numT.ToString()+
                    " numS ="+numS.ToString());
    //                Print “Error: TLeft is wrong”
    //Print “TLeft = ” TLeft
    //Print “NumT = ” NumT
    //Print “NumS = ” NumS”
            }//首先检查TLeft的值是否正确，错误则报错并退出。

            int BndLeft = (LBound - 2) * numS;
            int NumLeft = tleft;

            Cluster DCluster = getClusterbyID(0);

            #region// Each iteration assigns an element t0 of Cluster(0) to some Cluster(s) by Min Regret.
            for (int i = 0; i < tleft; i++)
            {
                if(BndLeft==NumLeft){
                    CheckBound = LBound;
                }else{
                    CheckBound = UBound;
                }
                double MinRegret = double.MaxValue;
                Element tCheck = DCluster.First;
                Element tBest = tCheck; ;
                int sBest = 0;

                #region//找到做小regret MinRegret 的element tBest和对应的cluster sBest
                while (tCheck != null)
                {
                    double BestVal1 = double.MaxValue;
                    double BestVal2 = double.MaxValue;
                    int s1Best = 0; 
                    int s2Best = 0;
                    for (int s = 1; s <= numS; s++)
                    {
                        Cluster curCluster = getClusterbyID(s);
                        if (curCluster.num < CheckBound)
                        {
                            double TrialVal=MoveVal[tCheck.ElementID,s];
                            if (TrialVal < BestVal2)
                            {
                                if (TrialVal < BestVal1)
                                {
                                    BestVal2 = BestVal1;
                                    s2Best = s1Best;
                                    BestVal1 = TrialVal;
                                    s1Best = s;//replace s2 with s1 ,s1 with s
                                }
                                else
                                {
                                    BestVal2 = TrialVal;
                                    s2Best = s;//replace s2with s
                                }
                            }
                        }
                    }//find the best 2 Cluster s1best and s2best

                    double Regret = BestVal1 - BestVal2;
                    if (Regret < MinRegret)
                    {
                        MinRegret = Regret;
                        tBest = tCheck;
                        sBest = s1Best;
                    }
                    tCheck = tCheck.After;
                }
                #endregion

                //MOve tBest from cLuster(0) to Cluster(sBest)
                tBest.MoveTo(this, sBest);
                Value[sBest] += AddVal[tBest.ElementID, sBest];
                double DeltaVal = MoveVal[tBest.ElementID, sBest];

                ObjVal += DeltaVal;////////////ObjVal is defined in Chapter2   and assigned in Chapter4.3
                ///////////////////////////////////////////////////////////ObjVal = ∑ (FullValue(s): s = 1 to NumS)
                /////////////////////////////////////////////////ObjVal = ObjVal + sValue

                Cluster Sa = getClusterbyID(sBest);
                Sa.NumberLinks += Sa.num-1;
                double SAValue = Value[sBest];
                double PresentFullValueA = SAValue / Sa.NumberLinks;
                //update values
                for (int t = 1; t <= numT ; t++)
                {
                    Element elementT = getElementbyID(t);
                    AddVal[t, sBest] += CalculateScore(elementT, tBest);
                    double FullAddValA = ((SAValue + AddVal[t, sBest]) / Sa.NumberLinks) - PresentFullValueA;
                    MoveVal[t, sBest] = FullAddValA;
                }//update done

                NumLeft = NumLeft - 1;
                if (Sa.num <= LBound)
                {
                    BndLeft--;
                }
            }
            #endregion

            if (DCluster.First != null)
            {
                throw new Exception("Error: First(0) ≠ 0:  First(0) = "+DCluster.First.ElementID.ToString());
            }

        }
        private int Min(int X, int Y)
        {
            if (X > Y)
                return Y;
            return X;

        }

        //add Element to the dummy Cluster
        public void AddElement2defaultCluster(Element t){
            Cluster tempcluster = (Cluster)clusterList[0];
            tempcluster.Add(t,0);
            elementList.Add(t);
        }

        public Cluster getClusterbyID(int id)
        {
            return (Cluster)clusterList[id];
        }

        public Element getElementbyID(int id)
        {
            return (Element)elementList[id-1];
        }

        public double CalculateScore(Element t1, Element t2)//坐标距离计算
        {
            double score = 0;
            if (t1 == null || t2 == null)
            {
                return double.MaxValue;
            }
            for (int i = 0; i < t1.AttributesX.Count; i++)
            {
                double tempscore = Convert.ToDouble(t1.AttributesX[i]) - Convert.ToDouble(t2.AttributesX[i]);
                if (tempscore < 0)
                {
                    tempscore = 0 - tempscore;
                }
                score +=  tempscore*tempscore;
            }
            return score;
        }


        public double Calculator(Cluster c)//return Value of Cluster s
        {
            double values = 0;
            Element em1 = c.First;
            Element em2 = c.First.After;
            for (int i = 0; i < c.num; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    values = values + CalculateScore(em1, em2);
                    em2 = em2.After;
                }
                em1 = em1.After;
            }
            return values;

        }

        public double FullvaluesCalculator(Cluster c)
        {
            c.NumberLinks = c.num * (c.num - 1) / 2;
            double values = Calculator(c);
            double fullvalues = values / c.NumberLinks;
            return fullvalues;
        }

        public double ObjValueCalculator()
        {
            double objvalues = 0;
            for (int i = 0; i < clusterList.Count; i++)
            {
                double tempfullvalues = FullvaluesCalculator(getClusterbyID(i));
                objvalues = objvalues + tempfullvalues;
            }
            return objvalues;
        }

        public ArrayList clusterList;
        public ArrayList elementList;
        private double StartWeight;//初始权重(为凸显某个因素的权)设为0.7
        private double Weight;
        private double large;
        private double ObjVal;
        private int numS;
        private int numT;
        private int UBound;
        private int LBound;

        private double[,] MoveVal;
        private double[,] AddVal;
        private double[] Value;
    }

}
